1. Field of the Invention
This invention relates to methods and systems for extracting melodic patterns in musical pieces and computer-readable storage medium having a program for executing the method.
2. Background Art
Extracting the major themes from a musical piece: recognizing patterns and motives in the music that a human listener would most likely retain (i.e. xe2x80x9cThematic extractionxe2x80x9d) has interested musician and AI researchers for years. Music librarians and music theorists create thematic indices (e.g., Kxc3x6chel catalog) to catalog the works of a composer or performer. Moreover, musicians often use thematic indices (e.g., Barlow""s A Dictionary of Musical Themes) when searching for pieces (e.g., a musician may remember the major theme, and then use the index to find the name or composer of that work). These indices are constructed from themes that are manually extracted by trained music theorists. Construction of these indices is time consuming and requires specialized expertise.
Theme extraction using computers has proven very difficult. The best known methods require some xe2x80x98hand tweakingxe2x80x99 to at least provide clues about what a theme may be, or generate thematic listings based solely on repetition and string length. Yet, extracting major themes is an extremely important problem to solve. In addition to aiding music librarians and archivists, exploiting musical themes is key to developing efficient music retrieval systems. The reasons for this are twofold. First, it appears that themes are a highly attractive way to query a music-retrieval system. Second, because themes are much smaller and less redundant, by searching a database of themes rather than full pieces, one can simultaneously get faster retrieval (by searching a smaller space) and get increased relevancy. Relevancy is increased as only crucial elements, variously named xe2x80x9cmotives,xe2x80x9d xe2x80x9cthemes,xe2x80x9d xe2x80x9cmelodiesxe2x80x9d or xe2x80x9chooks,xe2x80x9d are searched, thus reducing the chance that less important, but commonly occurring, elements will fool the system.
There are many aspects to music, such as melody, harmony, and rhythm, each of which may affect what one perceives as major thematic material. Extracting themes is a difficult problem for many reasons, among these are the following:
The major themes may occur anywhere in a piece. Thus, one cannot simply scan a specific section of piece (e.g., the beginning).
The major themes may be carried by any voice. For example, in FIG. 1, the principal theme is carried by the viola, the third lowest voice. Thus, one cannot simply xe2x80x9clistenxe2x80x9d to the upper voices.
There are highly redundant elements that may appear as themes, but should be filtered out. For example, scales are ubiquitous, but rarely constitute a theme. Thus, the relative frequency of a series of notes is not sufficient to make it a theme.
The U.S. patent to Larson (U.S. Pat. No. 5,440,756) discloses an apparatus and method for real-time extraction and display of musical chord sequences from an audio signal. Disclosed is a software-based system and method for real-time extraction and display of musical chord sequences from an audio signal.
The U.S. patent to Kageyama (U.S. Pat. No. 5,712,437) discloses an audio signal processor selectively deriving harmony part from polyphonic parts. Disclosed is an audio signal processor comprising an extracting device that extracts selected melodic part from the input polyphonic audio signal.
The U.S. patent to Aoki (U.S. Pat. No. 5,760,325) discloses a chord detection method and apparatus for detecting a chord progression of an input melody. Of interest is a chord detection method and apparatus for automatically detecting a chord progression of input performance data. The method comprises the steps of detecting a tonality of the input melody, extracting harmonic tones from each of the pitch sections of the input melody and retrieving the applied chord in the order of priority with reference to a chord progression.
The U.S. patent to Aoki (U.S. Pat. No. 6,124,543) discloses an apparatus and method for automatically composing music according to a user-inputted theme melody. Disclosed is an automated music composing apparatus and method. The apparatus and method includes a database of reference melody pieces for extracting melody generated data which are identical or similar to a theme melody inputted by the user to generate melody data which define a melody which matches the theme melody.
The Japanese patent document of Igarashi (JP3276197) discloses a melody recognizing device and melody information extracting device to be used for the same. Described is a system for extracting melody information from an input sound signal that compares information with the extracted melody information registered in advance.
The Japanese patent document of Kayano et al. (JP11143460) discloses a method for separating, extracting by separating, and removing by separating melody included in musical performance. The reference describes a method of separating and extracting melody from a musical sound signal. The sound signal for the melody desired to be extracted is obtained by synthesizing and adding the waveform based on the time, the amplitude, and the phase of the selected frequency component.
U.S. Pat. Nos. 5,402,339; 5,018,427; 5,486,646; 5,874,686; and 5,963,957 are of a more general interest.
An object of the present invention is to provide an improved method and system for extracting melodic patterns in a musical piece and computer-readable storage medium having a program for executing the method wherein such extraction is performed from abstracted representations of music.
Another object of the present invention is to provide a method and system for extracting melodic patterns in a musical piece and computer-readable storage medium having a program for executing the method, wherein the extracted patterns are ranked according to their perceived importance.
In carrying out the above objects and other objects of the present invention, a method for extracting melodic patterns in a musical piece is provided. The method includes receiving data which represents the musical piece, segmenting the data to obtain musical phrases, and recognizing patterns in each phrase to obtain a pattern set. The method further includes calculating parameters including frequency of occurrence for each pattern in the pattern set and identifying desired melodic patterns based on the calculated parameters.
The method may further include filtering the pattern set to reduce the number of patterns in the pattern set.
The data may be note event data.
The step of segmenting may include the steps of segmenting the data into streams which correspond to different voices contained in the musical piece and identifying obvious phrase breaks.
The step of calculating may include the step of building a lattice from the patterns and identifying non-redundant partial occurrences of patterns from the lattice.
The parameters may include temporal interval, rhythmic strength and register strength.
The step of identifying the desired melodic patterns may include the step of rating the patterns based on the parameters.
The step of rating may include the steps of sorting the patterns based on the parameters and identifying a subset of the input piece containing the highest-rated patterns.
The melodic patterns may be major themes.
The step of recognizing may be based on melodic contour.
The step of filtering may include the step of checking if the same pattern is performed in two voices substantially simultaneously.
The step of filtering may be performed based on intervallic content or internal repetition.
Further, in carrying out the above objects and other objects of the present invention, a system for extracting melodic patterns in a musical piece is provided. The system includes means for receiving data which represents the musical piece, means for segmenting the data to obtain musical phrases, and means for recognizing patterns in each phrase to obtain a pattern set. The system further includes means for calculating parameters including frequency of occurrence for each pattern in the pattern set and means for identifying desired melodic patterns based on the calculated parameters.
The system may further include means for filtering the pattern set to reduce the number of patterns in the pattern set.
The means for segmenting may include means for segmenting the data into streams which correspond to different voices contained in the musical piece, and means for identifying obvious phrase breaks.
The means for calculating may include means for building a lattice from the patterns and means for identifying non-redundant partial occurrences of patterns from the lattice.
The means for identifying the desired melodic patterns may include means for rating the patterns based on the parameters.
The means for rating may include means for sorting the patterns based on the parameters and means for identifying a subset of the input piece containing the highest-rated patterns.
The means for recognizing may recognize patterns based on melodic contour.
The means for filtering may include means for checking if the same pattern is performed in two voices substantially simultaneously.
The means for filtering may filter based on intervallic content or internal repetition.
Still further in carrying out the above objects and other objects of the present invention, a computer-readable storage medium is provided. The medium has stored therein a program which executes the steps of receiving data which represents a musical piece, segmenting the data to obtain musical phrases, and recognizing patterns in each phrase to obtain a pattern set. The program also executes the steps of calculating parameters including frequency of occurrence for each pattern in the pattern set and identifying desired melodic patterns based on the calculated parameters.
The program may further execute the step of filtering the pattern set to reduce the number of patterns in the pattern set.
The method and system of the invention automatically extracts themes from a piece of music, where music is in a xe2x80x9cnotexe2x80x9d representation. Pitch and duration information are given, though not necessarily metrical or key information. The invention exploits redundancy that is found in music: composers will repeat important thematic material. Thus, by breaking a piece up into note sequences and seeing how often sequences repeat, the themes are identical. Breaking up involves examining all note sequence lengths of two to some constant. Moreover, because of the problems listed earlier, one examines the entire piece and all voices. This leads to very large numbers of sequences, thus the invention uses a very efficient algorithm to compare these sequences.
Once repeating sequences have been identified, they are characterized with respect to various perceptually important features in order to evaluate their thematic value. These features are weighed for the thematic value function. For example, the frequency of a pattern is a stronger indication of thematic importance than pattern register. Hill-climbing techniques are implemented to learn weights across features. The resulting evaluation function then rates the sequence patterns uncovered in a piece.
The above objects and other objects, features, and advantages of the present invention are readily apparent from the following detailed description of the best mode for carrying out the invention when taken in connection with the accompanying drawings.